//https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=23253&ru=%2Fpractice%2Fff05d44dfdb04e1d83bdbdab320efbcb&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思路1:1.额外的vector，中序遍历的方式保存节点；2.重续调整指针指向；
//思路2:1.典型的中序遍历-递归实现 2.每次完成一个子模块的递归，更新下前驱节点；
		// 先思考下中序遍历怎么打印所有节点，然后每次打印的时候，把上一个节点记住一下；这样就串联起来了；
		// 不要考虑的太麻烦；


#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};



/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
  public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (pRootOfTree == nullptr) return nullptr;

        std::stack<TreeNode*> node_stack;
        TreeNode* node = pRootOfTree;

        std::vector<TreeNode*> node_vec;
        //记录上一个弹出的节点
        while (!node_stack.empty() || node != nullptr) {
            if (node != nullptr) {
                node_stack.push(node);
                node = node->left;
            } else {
                //从栈中取出元素
                node = node_stack.top();
                //中序遍历的节点得以保存且按顺序
                node_vec.push_back(node);
                node_stack.pop();
                //如果取出的节点还有右节点，那么就压入
                node = node->right;
            }
        }
        int length = node_vec.size();
        if (length == 1) return *node_vec.begin();
        // 遍历依次交换左右next指针
        for (int i = 0; i < length; ++i) {

            if (i == 0) {
                node_vec[i]->right = node_vec[i + 1];
				node_vec[i]->left = nullptr;

            } else if (i == (length - 1)) {
                node_vec[i]->left = node_vec[i - 1];
				node_vec[i]->right = nullptr;
            } else {
                node_vec[i]->right = node_vec[i + 1];
                node_vec[i]->left = node_vec[i - 1];
            }
        }
        return *node_vec.begin();

    }
};

class Solution {
  public:
    TreeNode* preNode = nullptr;//preNode一定是全局变量。
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (!pRootOfTree) return pRootOfTree;
        TreeNode* p = pRootOfTree;
        while (p->left) p = p->left;//找到双向链表的开头。
        inorder(pRootOfTree);
        return p;
    }

    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        //当前结点中需要进校的调整。
        root->left = preNode;
        if (preNode) {
            preNode->right = root;
        }
        preNode = root;//更新preNode，指向当前结点，作为下一个结点的前继。

        inorder(root->right);
    }
};


